package com.javabasic.algorithm.sword_of_offer;

import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see
 * @since Created by work on 2022/1/18 11:03 下午
 */
public class 剑指_Offer_13_机器人的运动范围 {


    int[][] unVisit;

    /**
     * 解法一：BFS+条件判断 解法
     * @param m
     * @param n
     * @param k
     * @return
     */
    public int movingCount(int m, int n, int k) {
        Coordination coordination = new Coordination(0, 0), currentNode;
        Queue<Coordination> queue = new LinkedList<>();
        queue.offer(coordination);

        int[][] NEXT = new int[][]{{-1,0},{0,1},{1,0},{0,-1}};
        int NEXT_LEN = 4, tempx, tempy, result = 0;
        unVisit = new int[m][n];
        unVisit[0][0] = 1;
        while (!queue.isEmpty()) {
            currentNode = queue.poll();
            result++;
            for (int i = 0; i < NEXT_LEN; i++) {
                tempx = currentNode.getX() + NEXT[i][0];
                tempy = currentNode.getY() + NEXT[i][1];
                if (validCoordination(tempx,tempy,m,n,k)) {
                    coordination = new Coordination(tempx, tempy);
                    unVisit[tempx][tempy] = 1;
                    queue.offer(coordination);
                }
            }
        }
        return result;
    }

    private boolean validCoordination(int tempx, int tempy, int m, int n, int k) {
        if (tempx < 0 || tempx >= m || tempy < 0 || tempy >= n || getCoordinationBitSum(tempx, tempy) > k || unVisit[tempx][tempy] == 1) {
            return false;
        }
        return true;
    }

    public int getCoordinationBitSum(int x, int y) {
        return getNumBitSum(x) + getNumBitSum(y);
    }

    private int getNumBitSum(int num) {
        int result = 0;
        while (num > 0) {
            result += num%10;
            num /= 10;
        }
        return result;
    }

    class Coordination {
        private int x;
        private int y;

        public Coordination(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Coordination that = (Coordination) o;
            return x == that.x && y == that.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }

        public int getX() {
            return x;
        }

        public void setX(int x) {
            this.x = x;
        }

        public int getY() {
            return y;
        }

        public void setY(int y) {
            this.y = y;
        }
    }
}
